在Two Sum 中 我們一開始最初的想法是用2次的loop檢查，那換做這3 Sum我們當然可以用三次loop來解，
時間複雜度直接飆升到Ｏ(n^3)。

還記得我們昨天最後一個方式嗎?
其實就是利用昨天用到的左右指針的方式。

舉一個Input Array: [12, 3, 1, 2, -6, 5, 0, -8, -1]
Target Sum: 0

如果以這題為例子，先把要檢查的陣列設定為
1.不是空陣列
2.陣列中每數都不同
來思考這題題目。

step1: 我們一樣先將陣列排序
step2: 從陣列的第一個數為主，依序找剩下的數中，可以照到兩個數和第一個數相加，最後達到目標總和

以下面例子來說

當我們把排序後的陣列開始檢查（也就是這裡的-8）
我們先把第一個數 -8 當作基準，往後(-6)開始尋找，開始找出兩個數，可以符合加上-8可以變成目標總和（0）

我們把左指標放在第一個基準數右邊，右指標一樣放在最後面。
以第一次來說，
我們可以得到 sum = -8 + -6 + 12 = -2
這個時候我們可以知道 -2 < 0
代表我們需要移動的是左指標，才可以加上更大的數，讓總和更接近0。
因為我們已經排序過這個陣列了

那如果我們遇到相加恰好等於目標總和時，應該要怎麼做？
這題題目要我們要找到所有符合的答案,而非一找到就停止，
所以我們應該要把左指標跟右指標一起移動才對，
這樣對於實作程式碼是不是有想法了？

那我們來討論一下時間複雜度吧！

我們知道要從第一個數開始去檢查到最後面的數，
而每次的基準數檢查都一樣要去確認剩下的數找出符合的兩數，
所以時間複雜度為Ｏ(n^2)
空間的複雜度上，因為我們一開始都需要把原本得陣列做排序來使用，
所以空間複雜度Ｏ(n)

如果我們依照上面的想法來實作，程式碼如下:

function threeNumberSum(array, targetSum) {
    array.sort((a, b) => a - b);
    const triplets = [];
    for (let i = 0; i < array.length - 2; i++) {
      let left = i + 1;
      let right = array.length - 1;
      while (left < right) {
        const sum = array[i] + array[left] + array[right];
        if (sum === targetSum) {
          triplets.push([array[i], array[left], array[right]]);
          left++;
          right--;
        } else if (sum < targetSum) {
          left++;
        } else if (sum > targetSum) {
          right--;
        }
      }
    }
    return triplets;
  }

不過這樣的解法可行的前提是，我們假設原本的陣列每一個數都不一樣。
而以Leetcode這題來說，targetSum = 0 ，所以如果排序完的第一個數是大於0的，
我們其實就可以完全不用繼續檢查了!
且“Notice that the solution set must not contain duplicate triplets.”
-> 不可以含重複的triplets

所以我們要多兩步檢查
1.重複的基準數要跳過
2.左右指針要移動的時候要先檢查下個數有沒有和自己一樣 -> 如果一樣，就要在往前多走一步

完整答案的做法如下：

var threeSum = function (nums) {
    nums.sort((a, b) => a - b);
    const triplets = [];

    for (let i = 0; i < nums.length - 2; i++) {
      if (nums[i] > 0) break;
      if (i > 0 && nums[i] === nums[i - 1]) continue;
      let left = i + 1;
      let right = nums.length - 1;
      while (left < right) {
        const sum = nums[i] + nums[left] + nums[right];
        if (sum === 0) {
          triplets.push([nums[i], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < 0) {
          left++;
        } else if (sum > 0) {
          right--;
        }
      }
    }
    return triplets;
  };

明日題目預告:
Squares of a Sorted Array